package nf.utility;

import java.util.Map;
import java.util.HashMap;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import nf.util.Rational;
import nf.graph.Node;
import nf.graph.Graph;
import nf.graph.Path;

/**
 * A utility calculator that divides value evenly amongst all nodes that appear
 * on some shortest path between two nodes.
 */
public class ComplexUtilityCalculator extends UtilityCalculator
{
	private static final int INFINITY = Integer.MAX_VALUE; // effectively inf.
	
	public Map<Node, Rational> getUtilities(Graph graph)
	{
		int nodeCount = graph.size();
		Map<Node, Rational> utilMap = new HashMap<Node, Rational>(nodeCount);
		Node[] nodes = new Node[nodeCount];
		Rational[] utils = new Rational[nodeCount];
		int[][] paths;
		int i, j, k;
		int pathLength;
		int inbound, outbound;
		//Rational change;
		HashSet<Integer> winningNodes = new HashSet<Integer>(nodeCount); 
		
		i = 0;
		for (Node n : graph) {
			utils[i] = new Rational(); // 0
			nodes[i] = n;
			++i;
		}
		
		// Calculate values
		paths = shortestPaths(nodes, graph);
		
		for (i = 0; i < nodeCount; ++i) {
			for (j = (i + 1); j < nodeCount; ++j) {
				if (paths[i][j] == INFINITY)
					continue;
				pathLength = paths[i][j];
				winningNodes.clear();
				
				for (k = 0; k < nodeCount; ++k) {
					inbound = paths[i][k];
					outbound = paths[k][j];
					
					if (inbound != INFINITY && outbound != INFINITY) {
						if (inbound + outbound == pathLength) {
							winningNodes.add(k);
						}
					}
				}
				
				Rational endChange = new Rational(1, pathLength+1);
				Rational middleChange = (new Rational(1)).subtract(endChange.multiply(new Rational(2)));
				if(winningNodes.size()-2 > 0) {
					middleChange = middleChange.divide(new Rational(winningNodes.size()-2));
				} else {
					middleChange = new Rational(0);
				}
				for (int nodeID : winningNodes) {
					if (nodeID == i || nodeID ==j) {
						traceValue(nodes[nodeID], endChange, nodes[i], nodes[j]);
						utils[nodeID] = utils[nodeID].add(endChange);
					} else {
					traceValue(nodes[nodeID], middleChange, nodes[i], nodes[j]);
						utils[nodeID] = utils[nodeID].add(middleChange);
					}
				}
			}
		}
		//System.err.println("---------");
		
		// Subtract edge costs
		for (i = 0; i < nodeCount; ++i) {
			List<Node> neighbors = graph.getNeighbors(nodes[i]);
			Rational utility = utils[i];
			
			for (Node neighbor : neighbors) {
				utility = utility.subtract(getEdgeCost(nodes[i], neighbor));
			}
			utilMap.put(nodes[i], utility);
		}
		
		return utilMap;
	}
	
	/**
	 * Finds the shortest paths between all nodes using the Roy-Floyd-Warshall
	 * algorithm.
	 */
	@SuppressWarnings("unchecked")
	private int[][] shortestPaths(Node[] nodes, Graph graph)
	{
		int n = nodes.length;
		int[][] paths = new int[n][n];
		int[] scoped;
		int i, j, k;
		int a, b;
		ArrayList<Node> allSteps;
		
		// Initialize the paths for direct neighbors.
		for (i = 0; i < n; ++i) {
			for (j = 0; j < n; ++j) {
				if (i == j) {
					paths[i][j] = 0;
				} else {
					paths[i][j] = (graph.connected(nodes[i], nodes[j]))
						? 1
						: INFINITY;
				}
			}
		}
		
		for (k = 0; k < n; ++k) {
			for (i = 0; i < n; ++i) {
				scoped = paths[i];
				for (j = 0; j < n; ++j) {
					a = scoped[j];
					b = scoped[k];
					
					if (paths[k][j] == INFINITY)
						b = INFINITY;
					else if (b != INFINITY && paths[k][j] != INFINITY)
						b += paths[k][j];
					
					/*System.err.printf("k=%d, i=%d, j=%d%n", k, i, j);
										System.err.printf("  %d, %d%n", a, b);*/
					if (b < a) {
						scoped[j] = b;
					}
				}
			}
		}
		
		return paths;
	}
}
